#include <iostream>

#include <climits>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>
#include <LEDA/system/basic.h>
#include "control.h"
#include <cmath>


#include <LEDA/core/queue.h>
#include <LEDA/core/p_queue.h>
#include <LEDA/graph/node_map.h>
#include <LEDA/graph/node_array.h>

using namespace leda;
using std::cout;
using std::endl;


#define DIRECTED true

/**
 * Get edge weight of a given edge e.
 */
double get_edge_weight(GraphWin & gw , edge e)
{
	string edge_label = gw.get_user_label(e);
	double weight = atof(edge_label.c_str());
	return weight;
}

/**
 * Bellman-Ford-algorithm to compute shortest paths in directed graphs with weighed edges.
 */
void bellmanFord(node &s ,graph &g, GraphWin &gw)
{

	//Queue for first phase of the algorithm
	queue<node> curr_q;
	queue<node> next_queue;
	next_queue.push(s);

	// used for counting until #(vertices - 1) then stops the algorithm
	int phase_counter = 0;

	// initialize distances to infinity
	node_array<double> dist(g, INFINITY);

	// array of the previous nodes in the optimal path from source
	node_array<node> from(g, NULL);

	// marker that will indicate whether a node is in a queue or not
	node_array<bool> marker(g,false);

	// set marker to true for the start node
	marker[s] = true;

	// set distance to start node to 0
	dist[s] = 0.0;
	gw.set_user_label(s , string("%g" , dist[s]));

	//START algorithm
	while (!next_queue.empty() && phase_counter < g.number_of_nodes() )
	{
		// next phase is about to start; increment phase counter
		phase_counter++;

		gw.message("Starting phase " + string("%i" , phase_counter));
		control_wait(1);

		// take next_queue as current queue for the current phase. this queue will be processed next
		curr_q = next_queue;

		// clear next queue, which will contain node for the next phase
		next_queue.clear();

		//mark nodes in current queue as 'next up' so we know which nodes will be visited in this phase.
		node v;
		forall(v, curr_q) {
	    	gw.set_color(v , green);
	    }
		control_wait(1);

		//START next phase
		while (!curr_q.empty()) {
			node source = curr_q.pop();
			//node source was popped, therefore it is no longer in a queue; fix marker
			marker[source] = false;

			//make border blue to indicate that this node is being active right now
			gw.set_border_width(source , 3);
			gw.set_border_color(source , blue);
			control_wait(0.5);
			edge e;
			forall_out_edges(e , source) {
				node target = g.target(e);
				double edge_weight = get_edge_weight(gw , e);

				if (dist[target] > dist[source] + edge_weight || dist[target] == INFINITY) {
					//update path length, backtracking
					dist[target] = dist[source] + edge_weight;
					from[target] = source;

					//show current distance
					gw.set_user_label(target , string("%g",dist[target]));
					//mark this edge as currently shortest path to this node.
					edge in_edge;
					forall_in_edges(in_edge , target) {
						gw.set_color(in_edge , grey3);
						gw.set_width(in_edge , 1);
					}
					gw.set_color(e , blue);
					gw.set_width(e , 3);

					// Add target node to queue for next phase
					// and mark it as added to avoid duplicates in the queue
					if (!marker[target]) {
						next_queue.push(target);
						marker[target] = true;
						gw.set_color(target , red);
						control_wait(0.5);
					}
				}
			}
			//reset border of node to indicate that it is no longer active
			gw.set_border_color(source , blue);
			gw.set_border_width(source , 1);

			//mark node as done
			gw.set_color(source , blue);
		}
		//END Phase
	}
	//END Algorithm

	if (!next_queue.empty()) {
		//We found a cycle!

		//First we color the whole graph blue
		node color_node;
		forall_nodes(color_node , g) {
			gw.set_color(color_node , blue);
		}

		edge color_edge;
		forall_edges(color_edge , g) {
			gw.set_color(color_edge , blue);
		}

		//next we mark the cycle red
		node start = next_queue.pop();

		node next = from[start];
		// First we get a node in the cycle.
		node_array<bool> cycle_marker(g,false);
		cycle_marker[start] = true;
		while(!cycle_marker[next]) {
			//mark node as visited once. When it gets visited again we know that we are in a cycle.
			cycle_marker[next] = true;
			//go back further
			next = from[next];
		}

		//now we traverse the cycle and color it red
		start = next;
		gw.set_color(start , red);
		next = from[next];
		while (start != next) {
			gw.set_color(next , red);
			next = from[next];
		}

		gw.acknowledge("A cycle was found and marked red.");
	}
}


int main(int argc, char *argv[])
{
    GraphWin gw(800, 600);
    gw.display();
    create_control();
    // set environment to display a directed / undirected graph depending on the DIRECTED constant
    gw.set_directed(DIRECTED);
    if (argc > 1)
        gw.read(argv[1]);
    gw.edit();
    graph &g = gw.get_graph();
    if (g.number_of_nodes() == 0) {
        gw.close();
        destroy_control();
        exit(1);
    }

    // initialize graph nodes and edges as grey3
    node v;
    edge e;
    forall_nodes(v, g)
    {
        gw.set_label_type(v, user_label);
        gw.set_color(v, grey3);
    }

    forall_edges(e, g)
    {
        gw.set_color(e, grey3);
    }

    //let user choose a node to start from
    while ((v = gw.read_node()) == NULL) ;

    //run bellmanFord algorithm starting from v
    bellmanFord(v , g , gw);

    gw.acknowledge("Ready!");
    gw.edit();
    gw.close();
    destroy_control();
    exit(0);
}
